/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Processamento;

import Visao.SimplexVisao;
import java.io.*;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 *
 * @author magelinha
 */
public class MetodosSimplex {
    
    public static String[] maximizacao;
    public static List<List<String>> lista = new ArrayList<List<String>>();
    public static int quantidadeVariaveis = 0;
    public static int maior = 0;
    public static int folga = 0;
    public static int quantidadeRestricoes = 0;
    public static double matrizSimplex[][];
    public static List<String> vetorVariaveis = new ArrayList<String>();
    public static List<String> vetorFolga = new ArrayList<String>();
    public static List<Double> vetorResultado = new ArrayList<Double>();
    DecimalFormat decimalFormat = new DecimalFormat("#,##0.00");
    public static List<Double> tempLinha = new ArrayList<Double>();
    static List<String> operacoes = new ArrayList<String>();
    
    /**
     * Esse método lê o arquivo da seguinte forma:
     * 
     * Primeira linha -> um inteiro que mostra a quantidade de variáveis;
     * Segunda linha -> função de maximização ex: 100 20 30 (100x1 + 20x2 + 30x3);
     * Da terceira linha em diante serão as equações de retrição que serão da mesma 
     * forma que a função de maximização.
     * 
     * Ex: 
     * 
     * 10  20 >= 15 (10x1 + 0x2 + 20x3 >= 15)
     *  15 40 <= 10 (0x1 + 15x2 + 40x3 >=10)
     * 
     * Os valores no arquivo SEMPRE são separados por espaço simples.
     * 
     * @param arquivo 
     */
    public void lerArquivo(File arquivo) throws FileNotFoundException, IOException{
        //limpa a lista
        lista.clear();
        FileReader reader = new FileReader(arquivo);
        BufferedReader leitor = new BufferedReader(reader);
        
        //leitura da primeira linha
        quantidadeVariaveis = Integer.valueOf(leitor.readLine());
        
        //leitura da segunda linha
        maximizacao = leitor.readLine().split(" ");
        
        //enquanto tiver funções de restrição ele vai lendo e inserindo na lista
        String linha = "";
        quantidadeRestricoes = 0;
        while((linha = leitor.readLine())!= null){
            
            lista.add(vetorStringParaLista(linha.split(" ")));
            quantidadeRestricoes++;
        }
        
        trocarVazioPorZero(lista);
        inserirVariaveisDeFolga(lista);
        reformularLista(lista);
        removerIgual();
        gerarMatriz();
        preencherVetoresComAsVariaveis();
    }
    
    /**
     * Método que insere as variáveis de folga. É feita a verificação no quantidadeVariavies item da lista.
     * Caso ele seja ">=" é inserido o valor -1 na posição quantidadeVariavies+1 da lista restrições;
     * Caso seja "<=" é inserido o valor 1 na posicao quantidadeVariavies+1 da lista restrições;
     * Caso contrário, nada é feito.
     * 
     * @param listaTemp 
     */
    
    public void inserirVariaveisDeFolga(List<List<String>> listaTemp){
        folga = 0;
        for(List<String> item: listaTemp){
            
            if(item.get(quantidadeVariaveis).equals(">=")){
                //preenche com 0 até o lugar da nova variável de folga
                for(int i=0; i<folga;i++){
                    item.add(quantidadeVariaveis + i,"0");
                }
                
                //insere a variável de folga;
                item.add(quantidadeVariaveis+folga, "-1");
                folga++;
                
                //transforma em equação
                item.set(item.size()-2, "=");
                
            }else if(item.get(quantidadeVariaveis).equals("<=")){
                //preenche com 0 até o lugar da nova variável de folga
                for(int i=0; i<folga;i++){
                    item.add(quantidadeVariaveis + i,"0");
                }
                
                //insere a variável de folga;
                item.add(quantidadeVariaveis+folga,"1");
                folga++;
                
                //transforma em equação
                item.set(item.size()-2, "=");
                
            }
        }   
    }
    
    /**
     * Para que os valores não sejam alterados na matriz, a linha do pivo é passada pra uma lista auxiliar
     * @param linhaDoPivo 
     */
    public void preencherListaTemp(int linhaDoPivo){
        tempLinha.clear();
        for(int i=0; i<quantidadeVariaveis+folga+2;i++){
            tempLinha.add(matrizSimplex[linhaDoPivo][i]);
        }
    }
    
    /**
     * Troca todas as posições vazias por 0, isso servirá para facilitar na construção do tableu simplex
     * @param listaTemp 
     */
    public void trocarVazioPorZero(List<List<String>> listaTemp){
        for(int i=0; i<listaTemp.size();i++){
            for(int j=0; j< listaTemp.get(i).size(); j++){
                if(listaTemp.get(i).get(j).equals("")){
                    listaTemp.get(i).set(j, "0");
                }
            }
        }
    }
    
    /**
     * O método String.split() retornar um String[], para facilitar a inserção
     * de dados é feita a conversão para uma lista, podendo assim inserir dados
     * em qualquer posição.
     * @param vetor
     * @return 
     */
    public List<String> vetorStringParaLista(String[] vetor){
        List<String> convertida = new ArrayList<String>();
        convertida.addAll(Arrays.asList(vetor));
        
        return convertida;
    }
    
    
    /**
     * Após inserir as variáveis de folga, as listas ficaram com tamanhos diferentes.
     * Para facilitar a criação do tableu, vamos deixar todas as listas com mesmo tamanho
     * @param listaTemp 
     */
    public void reformularLista(List<List<String>> listaTemp){
        //verifica qual a lista de maior tamanho;
        maior = 0;
        for(List<String> item: listaTemp){
            if(item.size() > maior) maior = item.size();
        }
        
        /*
         * faz com que todas as listas tenham o mesmo tamanho adicionando sempre antes 
         * do = o valor 0
         * 
         */
        
        for(List<String> item: listaTemp){
            while(item.size() < maior){
                item.add(item.size()-2, "0");
            }
        }
        
    }
    
    /**
     * A partir da lista de restrições e da matriz de maximização é possivel criar o tableu.
     * A primeira linha da matriz fica por conta da função de maximização. Como as variáveis
     * são sempre positivas, o primeiro item da matriz será sempre -1 e o resto da primeira linha
     * será composta pelos item da matriz de maximização, com excessão do último item, que será 0.
     * 
     * As outros linhas da matriz terão o primeiro item 0 e os outros item, serão compostos pelas listas
     * de restrições.
     */
    public void gerarMatriz(){
        System.out.println("quantidade restricoes: " + quantidadeRestricoes);
        System.out.println("folga: " + folga);
        preencherPrimeiraColunaDaMatriz();
        preencherPrimeiraLinhaDaMatriz();
        inserirRestricoesNaMatriz();
    }
    
    /**
     * Como esse trabalho será baseado somente em variáveis positivas, a primeira coluna já é conhecida.
     * 
     * O primeiro item é -1 (valor de Z);
     * Os outros itens tem valor 0;
     */
    public void preencherPrimeiraColunaDaMatriz(){
        //Define o tamanho da matriz
        //A quantidade de linhas é a soma de todas as veriaveis mais o Z e o B.
        matrizSimplex = new double[quantidadeRestricoes + 1][quantidadeVariaveis + folga + 2];
        matrizSimplex[0][0] = -1;
        
        for(int i=1;i<quantidadeRestricoes + 1;i++){
            matrizSimplex[i][0] = 0;
        }
    }
    
    /**
     * Copia a matriz inicial para verificação de soluções ilimitadas
     * @return 
     */
    public double[][] copiarMatrizInicial(){
        double[][] copia = new double[quantidadeRestricoes+1][quantidadeVariaveis + folga + 2];
        
        for(int i=0; i< quantidadeRestricoes + 1; i++){
            for(int j=0;j<quantidadeVariaveis + folga + 2;j++){
                copia[i][j] = matrizSimplex[i][j];
            }
        }
        return copia;
    }
    
    /**
     * A primeira linha é composta pelos itens do vetor de maximização e o último elemento é 0
     */
    public void preencherPrimeiraLinhaDaMatriz(){
        for(int i=0;i < quantidadeVariaveis+folga;i++){
            if(i<maximizacao.length){
                matrizSimplex[0][i+1] = Integer.valueOf(maximizacao[i]);
            }else{
                matrizSimplex[0][i+1] = 0;
            }
            
        }
        matrizSimplex[0][quantidadeVariaveis + folga + 1] = 0;
    }
    
    /**
     * Insere as funções de restrição da lista na matriz
     */
    public void inserirRestricoesNaMatriz(){
        imprimirLista();
        for(int i= 1; i< quantidadeRestricoes + 1;i++){
            for(int j = 1; j< quantidadeVariaveis + folga + 2;j++){
                matrizSimplex[i][j] = Double.valueOf(lista.get(i-1).get(j-1));
            }
        }
    }
    
    /**
     * Imprime os itens da lista. Será usada apenas como teste.
     */
    public void imprimirLista(){
        for(List<String> item: lista){
            for(String s: item){
                System.out.print(s + " ");
            }
            System.out.println();
        }
    }
    
    /**
     * Insere as variaveis num vetor para preencher a tabela
     */
    public void preencherVetoresComAsVariaveis(){
        int j = 0;
        char aux = 'a';
        String variavel = "a";
        vetorVariaveis.add("z");vetorFolga.add("z");
        for(int i=0; i< quantidadeVariaveis + folga; i++){
            variavel = String.valueOf(aux++);
            if(i>=quantidadeVariaveis){
                vetorFolga.add(variavel);
            }
            vetorVariaveis.add(variavel);
        }
        
        vetorVariaveis.add(String.valueOf(aux++));
    }
    
    /**
     * Percorre a lista remover itens de valor "="
     */
    public void removerIgual(){
        for(List<String> item: lista){
            item.remove("=");
        }
        maior--;
    }
    
    /**
     * Percorre a primeira linha da matriz e verifica qual é a coluna que contem o item de menor valor e seja maior que 0.
     * Ao escolher esse item, é feita uma varrredura nessa coluna verificando qual o menor valor resultante da divisão entre 
     * o item da coluna e o ultimo item da linha.
     * 
     * Em caso de empate na saída é utilizada a regra de Bland
     * @return 
     */
    public List<Integer> escolherPivo(){
        List<Integer> pivos = new ArrayList<Integer>();
        int coluna =0;
        double valor = 0;
        
        for(int i=0; i < quantidadeVariaveis + folga + 2; i++){
            if(matrizSimplex[0][i] > 0 && matrizSimplex[0][i] > valor){
                valor = matrizSimplex[0][i];
                coluna = i;
            }
        }
        
        if(valor == 0){
            pivos.clear();
            return pivos;
        }
        
        pivos.add(coluna);
        valor = Integer.MAX_VALUE;
        boolean empate = false;
        boolean menorQueZero = false;
        int linha = 0;
        for(int i=1; i < quantidadeRestricoes + 1; i++){
            if(matrizSimplex[i][coluna] >= 1){
                menorQueZero = true;
            }
            
            if(matrizSimplex[i][quantidadeVariaveis+folga+1] != 0 && 
                    matrizSimplex[i][quantidadeVariaveis+folga+1]/matrizSimplex[i][coluna] < valor){
                
                valor = matrizSimplex[i][quantidadeVariaveis+folga+1]/matrizSimplex[i][coluna];
                linha = i;
            }else if(matrizSimplex[i][quantidadeVariaveis+folga+1] != 0 && 
                    matrizSimplex[i][quantidadeVariaveis+folga+1]/matrizSimplex[i][coluna] == valor){
                empate = true;
            }
        }
        
        if(!menorQueZero){
            pivos.clear();
            pivos.add(-1);
            return pivos;
        }
        if(empate){
            valor = Integer.MAX_VALUE;
            for(int i=1; i < quantidadeRestricoes + 1; i++){
                if(matrizSimplex[i][coluna] > 0 && matrizSimplex[i][coluna] < valor){
                    valor = matrizSimplex[i][coluna];
                    linha = i;
                }
            }
        }
        
        pivos.add(linha);
        //remove os zeros da lista
        Iterator it = pivos.iterator();
        while(it.hasNext()){
            if(Double.valueOf(it.next().toString()) == 0){
                it.remove();
            }
        }
        
        return pivos;
    }
    
    /**
     * define as operações de soma ou subtração após escolher o pivo.
     * @param linha
     * @param coluna
     * @param valor 
     */
    public void operacoes(int linha, int coluna, double valor){
        operacoesComPivo(linha, valor);
        operacoesEntreLinhas(linha, coluna);
    }
    
    public void operacoesComPivo(int linha,double valor){
        operacoes.clear();
        operacoes.add("L" + String.valueOf(linha) + " = L" + String.valueOf(linha) + "/" + decimalFormat.format(valor));
        for(int i=0; i < quantidadeVariaveis+folga+2;i++){
            matrizSimplex[linha][i] /= valor;
        }
    }
    
    /**
     * Realiza efetivamente as operações entre a linha do pivô e as outras. Essas operação serão mostradas no painel
     * através da lista de retorno.
     * @param linha
     * @param coluna
     * @return 
     */
    public List<String> operacoesEntreLinhas(int linha, int coluna){
        operacoesComPivo(linha, matrizSimplex[linha][coluna]);
        
        String tipoOperacao = "";
        for(int i=0; i< quantidadeRestricoes+1; i++){
            if(i != linha){
                
                //determino ser vai se a operação será de soma ou subtracao
                if(matrizSimplex[i][coluna] < 0) tipoOperacao = " + ";
                else tipoOperacao = " - ";
                
                //mensagem que será mostrada na tela
                operacoes.add("L" + String.valueOf(i) + " = L" +  
                        String.valueOf(i) + tipoOperacao + decimalFormat.format(Math.abs(matrizSimplex[i][coluna])) + 
                        "L" + String.valueOf(linha));
                
                preencherListaTemp(linha);
                operacaoLinha(linha, i, tipoOperacao, Math.abs(matrizSimplex[i][coluna]));
            }
        }
        
        return operacoes;
    }
    
    
    /**
     * Subtrai, ou soma uma linha com a outra. Isso é determinada pela String operacao, caso seja " - " é feita uma subtracao,
     * caso contrário é feita a soma.
     * @param linhaPivo
     * @param linhaLoop
     * @param operacao 
     */
    public void operacaoLinha(int linhaPivo, int linhaLoop, String operacao, double coeficiente){
        int valor = 1;
        if(operacao.equals(" - ")) valor = (-1);
        else valor = 1;
        
        for(int i=0; i < quantidadeVariaveis +folga+2;i++){
            matrizSimplex[linhaLoop][i] += tempLinha.get(i) * valor * coeficiente;
        }
    }
    
    public static void alterarBase(int linha, int coluna){
        vetorFolga.set(linha, vetorVariaveis.get(coluna));
    }
    
    /**
     * Será chamando quando o simplex retornar o resultado final.
     * 
     * Será verificado na lista "vetorFolga" quais são as variáveis que estão na base
     * 
     * Como a lista "vetorResultado" possuirá o mesmo tamanho da lista "vetorVariaveis", basta inserir
     * no mesmo indice o valor referente ao vetor B
     */
    public static void preencherListResultado(){
        vetorResultado.clear();
        //preenche tudo com 0
        for(int i=0;i<vetorVariaveis.size()-2;i++){
            vetorResultado.add(0.);
        }
        
        //percorre as variáveis que ficaram na base
        for(int i=1; i<vetorFolga.size();i++){
            //verifica qual o valor referente no vetor B, que no caso
            //é a última coluna da matriz
            double valor = matrizSimplex[i][quantidadeVariaveis + folga + 1];
            
            //verifico qual o indice da variavel que esta na base na lista
            //"vetorVariaveis"
            for(int j=1; j<vetorVariaveis.size()-1;j++){
                if(vetorFolga.get(i).equals(vetorVariaveis.get(j))){
                    vetorResultado.set(j-1, valor);
                    break;
                }
            }
        }
    }
    
    
    
    public List<Double> copiarVetorResultado(){
        List<Double> copia = new ArrayList<Double>();
        copia.addAll(vetorResultado);
        return copia;
    }
    
    public void imprimirVetorResultado(){
        for(int i=0; i<vetorVariaveis.size()-2;i++){
            System.out.println("posicao: " + i + "   valor: " + vetorResultado.get(i));
        }
    }

    @Override
    public String toString() {
        preencherListResultado();
        String resultado = "{";
        if(!SimplexVisao.multiplasSolucoes){
            for(int i=0; i<vetorResultado.size();i++){
                if(i == vetorResultado.size()-1){
                    resultado+= vetorResultado.get(i) + "}";
                }else{
                    resultado+= vetorResultado.get(i) + ", ";
                }

            }
        }else{
            resultado = "α[";
            
            SimplexVisao.listaMultiplasSolucoes.add(vetorResultado);
            
            for(int j=0; j< SimplexVisao.listaMultiplasSolucoes.size();j++){
                if(j == 0){
                    for(int i=0; i<vetorResultado.size();i++){
                        if(i == vetorResultado.size()-1){
                            resultado+= SimplexVisao.listaMultiplasSolucoes.get(0).get(i) + "] + (α+1)[";
                        }else{
                            resultado+= SimplexVisao.listaMultiplasSolucoes.get(0).get(i) + ", ";
                        }
                    }
                }else{
                    for(int i=0; i<SimplexVisao.listaMultiplasSolucoes.get(1).size();i++){
                        if(i == vetorResultado.size()-1){
                            resultado+= SimplexVisao.listaMultiplasSolucoes.get(1).get(i) + "]";
                        }else{
                            resultado+= SimplexVisao.listaMultiplasSolucoes.get(1).get(i) + ", ";
                        }
                    }
                }
            }
            
        }
        
        
        return resultado;
    }
    
    /**
     * Método que servirá para verificar se ocorrem múltiplas soluções ótimas.
     * Percorre todas as colunas, caso encontre algum valor > 1 nas equações de restrição, indica que essa posição 
     * é o novo pivô.
     * 
     * Retorna uma lista onde o primeiro é a linha e o segundo é a coluna do pivô.
     * @return 
     */
    public List<Integer> verificarMultiplasSolucoes(){
        List<Integer> temp = new ArrayList<Integer>();
        
        for(int i=1; i < quantidadeVariaveis+folga+1;i++){
            for(int j=1;j<quantidadeRestricoes+1;j++){
                if(matrizSimplex[j][i] > 1){
                    System.out.println("valor: " + matrizSimplex[j][i]);
                    temp.add(i);
                    temp.add(j);
                    System.out.println("j: " + j + "  i: " + i);
                    return temp;
                }
            }
        }
        
        return temp;
    }
    
    /**
     * Caso em algum passo seja verificado que chegou novamente ao estado inicial, indica que a solução é ilimitada
     * @param matrizInicial
     * @param matrizCopia
     * @return 
     */
    public boolean solucaoIlimitada(double[][] matrizInicial, double[][] matrizCopia){
        System.out.println("Comparação \n\n");
        
        for(int i=0; i<quantidadeRestricoes+1;i++){
            for(int j=0;j<quantidadeVariaveis+folga+2;j++){
                if(matrizInicial[i][j] != matrizCopia[i][j]){
                    return false;
                }
            }
        }
        
        return true;
    }
    
    
}
